package tree;

import java.util.LinkedList;

/**
 * @author kaho
 * @since 2021/3/12
 */
public class _331_验证二叉树的前序序列化 {

    /**
     * 序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
     * @param preorder
     * @return
     */
    public static boolean isValidSerialization1(String preorder) {

        String[] split = preorder.split(",");
        int diff = 1;
        for (int i = 0; i < split.length; i++) {
            diff -=1;
            if (diff<0){
                return false;
            }else if(!split[i].equals("#")){
                diff+=2;
            }
        }
        return diff == 0;

    }
    public static boolean isValidSerialization(String preorder) {
        LinkedList<String> stack = new LinkedList<>();
        String[] split = preorder.split(",");
        for (String s : split) {
            stack.push(s);

            while (stack.size() > 2
                    && "##".equals(stack.get(0) + stack.get(1))
                    && !"#".equals(stack.get(2))) {
                for (int j = 0; j < 3; j++) {
                    stack.pop();
                }
                stack.push("#");
            }
        }
        return stack.size()==1 && "#".equals(stack.peek() );
    }

    public static void main(String[] args) {
        boolean validSerialization = isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#");
    }
}
